import java.util.LinkedList;
import java.util.List;

/**
 * Created by L.jp
 * Description:给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。
 *
 * 叶子节点 是指没有子节点的节点。

 * User: 86189
 * Date: 2022-12-09
 * Time: 23:53
 */
class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode() {}
      TreeNode(int val) { this.val = val; }
      TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
          this.right = right;
      }
}
/*
*       返回的是一个嵌套的数组，存储的是最终结果，那么嵌套数组里面的每一个元素就是一个符合结果的路径，
* 并且每一个元素list在加入结果集时都需要复制一份新的
*
* */
public class Solution {
    List<List<Integer>> result=new LinkedList<>();
    LinkedList<Integer> tmp=new LinkedList<>();
    public List<List<Integer>> pathSum(TreeNode root, int target) {
        dfs(root,target);
        return result;
    }
    public void dfs(TreeNode root, int target) {
        if(root==null){
            return;
        }
        //节点不为空，加入临时存储数组
        tmp.add( root.val );
        //那么目标值减去当前值
        target-=root.val;
        //当抵达叶子节点并且目标和为0的时候，就把遍历的路径加入结果集
        if(target==0 && root.left==null && root.right==null){
            result.add( new LinkedList<>(tmp) );
        }
        //加入左右节点的值
        dfs( root.left,target );
        dfs( root.right,target );
        //回溯，删除最后一个，向上回溯
        tmp.removeLast();
    }

}
